package dp.路径;

import java.util.ArrayList;
import java.util.List;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 杨辉三角118.java
 * @Description https://leetcode-cn.com/problems/pascals-triangle/
 * @createTime 2021年11月08日 20:37:00
 */
public class 杨辉三角118 {
	public List<List<Integer>> generate(int numRows) {
		List<List<Integer>> list = new ArrayList<>();

		//定义备忘录dp[i][j] 表示 第 i 行  第 j 列的数值
		int[][] dp = new int[numRows][numRows];

		//初始化转态，第dp[0][0]=1;
		dp[0][0] = 1;

		/**
		 * 转态转移方程
		 *  当 j= 0的时候 dp[i][j]=1
		 *  当 j !=0 的时候  dp[i][j]=dp[i-1]dp[j-1]+dp[i-1][j]
		 */

		for (int i = 1; i < numRows; i++) {
			for (int j = 0; j <= i; j++) {
				if (j == 0) {
					dp[i][j] = 1;
				} else {
					dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
				}
			}
		}
		//进行结果转换

		for (int i = 0; i < dp.length; i++) {
			List<Integer> tmp = new ArrayList<>();
			for (int j = 0; j < dp.length; j++) {
				if (dp[i][j] == 0) {
					break;
				}
				tmp.add(dp[i][j]);
			}
			list.add(new ArrayList<>(tmp));
		}
		return list;
	}
}
